package collections;

import util.Tracer;

public class RadixTree {
	private RadixTreeNode root;
	
	public RadixTree() {
		root = new RadixTreeNode();
	}
	
	public void insert(String bStr)
	{
		RadixTreeNode node = root;
		for(int i = 0, length = bStr.length(); i < length; i ++)
		{
			char ch = bStr.charAt(i);

			RadixTreeNode child;
			if(ch == '0')
			{
				child = node.getLeftChild();
			}
			else
			{
				child = node.getRightChild();
			}

			if(child == null)
			{
				child = new RadixTreeNode();
				
				if(ch == '0')
				{
					node.setLeftChild(child);
				}
				else
				{
					node.setRightChild(child);
				}
			}
			
			node = child;
		}
		
		node.setKey(bStr);
	}
	
	public void printSorted()
	{
		printSorted(root);
	}
	
	private void printSorted(RadixTreeNode node)
	{
		if(node == null) return;
		
		if(node.getKey() != null)
		{
			Tracer.trace(node.getKey());
		}
		
		printSorted(node.getLeftChild());
		printSorted(node.getRightChild());
	}
	
	public static void main(String[] args) {
		RadixTree tree = new RadixTree();
		tree.insert("0001");
		tree.insert("1001");
		tree.insert("0101");
		tree.insert("0000");
		tree.insert("1101");
		tree.insert("100");
		
		tree.printSorted();
	}
}
